/* ***** BEGIN LICENSE BLOCK *****
 * Version: NPL 1.1/GPL 2.0/LGPL 2.1
 *
 * The contents of this file are subject to the Netscape Public License
 * Version 1.1 (the "License"); you may not use this file except in
 * compliance with the License. You may obtain a copy of the License at
 * http://www.mozilla.org/NPL/
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * The Original Code is lutsko.com code.
 *
 * The Initial Developer of the Original Code is  James Lutsko 
 * (jim@lutsko.com http://www.lutsko.com).
 * Portions created by the Initial Developer are Copyright (C) 2003
 * the Initial Developer. All Rights Reserved.
 *
 * Contributor(s):
 *
 *
 * Alternatively, the contents of this file may be used under the terms of
 * either the GNU General Public License Version 2 or later (the "GPL"), or
 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 * in which case the provisions of the GPL or the LGPL are applicable instead
 * of those above. If you wish to allow use of your version of this file only
 * under the terms of either the GPL or the LGPL, and not to allow others to
 * use your version of this file under the terms of the NPL, indicate your
 * decision by deleting the provisions above and replace them with the notice
 * and other provisions required by the GPL or the LGPL. If you do not delete
 * the provisions above, a recipient may use your version of this file under
 * the terms of any one of the NPL, the GPL or the LGPL.
 *
 * ***** END LICENSE BLOCK ***** */
/*
*   Copyright (c) 2003 James Lutsko (jim@lutsko.com, http://www.lutsko.com).  All Rights Reserved.
*
*   The author makes no representations or warranties about the suitability of the
*   software, either express or implied, including but not limited to the
*   implied warranties of merchantability, fitness for a particular
*   purpose, or non-infringement. The author shall not be liable for any damages
*   suffered by licensee as a result of using, modifying or distributing
*   this software or its derivatives.
*
*   The author requests that he be notified of any application, applet, or other binary that
*   makes use of this code and that some acknowedgement is given. Comments, questions and
*   requests for change will be welcomed.
*/


package autoschedule;

import java.util.Iterator;
import java.util.Vector;

public class AutoSchedule
{
    Vector Matches = null;
    int N;

    public void rotate(int[] t1, int[] t2, int round)
    {
	for(int i=0;i<t1.length;i++,round++)
	    {
		if(Matches.size() < round+1)
		    {
			int[] m = new int[N];
			for(int j = 0;j<N;j++)
			    m[j] = -1;
			Matches.add(m);
		    }

		int[] match = (int[]) Matches.get(round);
		for(int j=0;j<t1.length;j++)
		    {
			int index = (j-i)%(t1.length);
			if(index < 0) index += t1.length;

			if(t1[j] >= 0)
			    match[t1[j]] = t2[index];
			if(t2[index] >= 0) 
			    match[t2[index]] = t1[j];
		    }
	    }
    }


    void doSchedule(int[] t, int round, int marker)
    {
	int[] t1 = null;
	int[] t2 = null;
	
	int len = ((t.length)%2 == 0 ? t.length/2 : (t.length+1)/2);
	t1 = new int[len];
	t2 = new int[len];
	for(int i=0;i<len-1;i++) 
	    {
		t1[i] = t[i]; 
		t2[i] = t[i+len];
	    }
	t1[len-1] = t[len-1];
	t2[len-1] = (t.length%2 == 0 ? t[2*len-1] : marker);

	rotate(t1,t2,round);
	round += t1.length;

	// Re-order the second half of the array ...
	// (just requires rotating through t1.length)
	// ... and update the marker
	if(t1.length%2!=0) 
	    {
		for(int i=0;i<t1.length;i++)
		    {
			int index = (i-(t1.length-1)); //%(t1.length);
			if(index < 0) index += t1.length;
			if(index+len == t.length)
			    t2[i] = marker;
			else t2[i] = t[index+len];
		    }
		marker = -round+1;
	    }
	if(t1.length > 1) doSchedule(t1,round,marker);
	if(t2.length > 1) doSchedule(t2,round,marker);			
    }

    void cleanup()
    {
	int[] toRemove = new int[Matches.size()];
	for(int i=0;i<toRemove.length;i++) toRemove[i] = 0;
	for(Iterator I = Matches.iterator();I.hasNext();)
	    {
		int[] m = (int[]) I.next();
		for(int i=0;i<m.length;i++)
		    if(m[i] < 0)
			{
			    int index = -m[i];
			    toRemove[index] = 1;
			    m[i] = ((int[]) Matches.get(index))[i];
			}
	    }
	
	for(int j = toRemove.length-1;j>=0;j--)
	    if(toRemove[j] > 0)
		Matches.remove(j);			    
    }

    public AutoSchedule(int n)
    {
	N = n;

	int[] t = new int[N];
	for(int i=0;i<N;i++) 
		t[i] = i; 

	Matches = new Vector();
	for(int i=0;i<N-1;i++)
	    {
		int[] m = new int[N];
		for(int j = 0;j<N;j++)
		    m[j] = -1;
		Matches.add(m);
	    }

	doSchedule(t,0,-2);

	// clean up

	cleanup();
	/*
	int i = 0;
	for(Iterator I = Matches.iterator();I.hasNext();)
	    {
		int[] m = (int[]) I.next();
		String s = "" + i++ + ": ";
		for(int j=0;j<N;j++)
		    s += m[j] + "  ";
		System.out.println(s);
	    }
	*/
    }

    public static void main(String args[])
    {
	if(args.length < 1) return;

	int n = Integer.parseInt(args[0]);
	AutoSchedule a = new AutoSchedule(n);

    }
}
